<?php

class ConsistentHashing
{
    private $nodes = array();
    private $vnum = 64;
    private $_ring = array();

    function __construct()
    {
        if(!empty($this->node))
        {
            foreach ($this->nodes as $v)
            {
                $this->addNode($v);
            }
        }
    }

    function time33($str)
    {
        $hash = 0;
        $len = 32;
        $str = md5($str);
        $speed = 5;
        for($i=0;$i<$len;$i++)
        {
            $hash = ($hash << $speed) + $hash + ord($str[$i]);
        }

        return $hash & 0x7FFFFFFF;
    }

    function addNode($node)
    {
        for($i=0;$i<$this->vnum;$i++)
        {
            $hash = $this->time33($node.'#'.$i);
            if(!isset($this->_ring[$hash]))
            {
                $this->_ring[$hash] = $node.'#'.$i;
            }
        }
    }

    function get_ring()
    {
        ksort($this->_ring);
        var_dump($this->_ring);
    }
    function getNode($key)
    {
        ksort($this->_ring);
//        var_dump($this->_ring);
        $hash = $this->time33($key);
        $keys = array_keys($this->_ring);
        $low = 0;
        $high = sizeof($keys)-1;
        while ($low < $high-1)
        {
            $mid = floor(($low+$high)/2);

            if($keys[$mid] >= $hash) $high = $mid;
            else $low = $mid;
        }

        $node = $keys[$high];
        return $this->_ring[$node];

    }


}

//echo ConsistentHashing::time33('test12');
$obj = new ConsistentHashing();
$obj->addNode('server1');
$obj->addNode('server2');
//$obj->get_ring();
var_dump($obj->getNode('keys1'));
var_dump($obj->getNode('keys2'));
var_dump($obj->getNode('keys3'));
var_dump($obj->getNode('keys4'));